package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code68MedianOfTwoSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int k;
        if (((m + n) & 1) == 0) {
            // 偶数情况下, 中位数为 len / 2 和 len / 2 + 1 的平均数
            k = (m + n) / 2;
            return (double) (getKth(nums1, 0, m - 1, nums2, 0, n - 1, k) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, k + 1)) / 2;
        } else {
            // 奇数情况下, 中位数下标为 k = len / 2, 即第 k 小的数
            k = (m + n) / 2 + 1;
            return (double) getKth(nums1, 0, m - 1, nums2, 0, n - 1, k);
        }
    }

    private int getKth(int[] nums1, int l1, int r1, int[] nums2, int l2, int r2, int k) {
        int m = r1 - l1 + 1;
        int n = r2 - l2 + 1;

        if (m > n) {
            // 始终将长的数组放在 nums2
            return getKth(nums2, l2, r2, nums1, l1, r1, k);
        }
        if (m == 0) {
            // nums1 为空数组时, 直接取 nums2 第 k 小的数
            return nums2[l2 + k - 1];
        }
        if (k == 1) {
            // 第一小的数
            return Math.min(nums1[l1], nums2[l2]);
        }
        // nums1 中第 k / 2 小的数 m1
        int i = l1 + Math.min(m, k / 2) - 1;
        // nums2 中第 k / 2 小的数 m2
        int j = l2 + Math.min(n, k / 2) - 1;
        if (nums1[i] > nums2[j]) {
            // 丢掉 nums2 中左边的数, k 相应减小, 对应二分的 l = m2 + 1
            return getKth(nums1, l1, r1, nums2, j + 1, r2, k - (j - l2 + 1));
        } else {
            return getKth(nums1, i + 1, r1, nums2, l2, r2, k - (i - l1 + 1));
        }
    }
}
